// https://www.lintcode.com/problem/decode-ways/description
// 描述
// 有一个消息包含A-Z通过以下规则编码
// 'A' -> 1
// 'B' -> 2
// ...
// 'Z' -> 26
// 现在给你一个加密过后的消息，问有几种解码的方式
// 样例
// 给你的消息为12，有两种方式解码 AB(12) 或者 L(12). 所以返回 2

class Solution {
public:
    /**
     * @param s: a string,  encoded message
     * @return: an integer, the number of ways decoding
     */
    int numDecodings(string &s) {
        // int l = s.length();
        // if (l == 0)
        // {
        //     return 0;
        // }
        // int *ways = new int[l + 1];
        // ways[0] = 1;
        // for (int i = 1; i < l + 1; i++) 
        // {
        //     if (s[i - 1] != '0')
        //     {
        //         ways[i] += ways[i - 1];
        //     } 
        //     if ( i != 1 && ((s[i - 2] - '0') * 10 + s[i - 1] - '0' > 0) && ((s[i - 2] - '0') * 10 + s[i - 1] - '0' <= 26))
        //     {
        //         ways[i] += ways[i - 2];
        //     } 
        // }
        // return ways[l];
    int l = s.length();
    if (l == 0) {
      return 0;   // only for this problem, but the ans should be 1
    }
    vector<int> f(l + 1);
    f[0] = 1;
    
    for (int i = 0; i < l; i++) {
      f[i + 1] = 0;
      if (s[i] != '0') {
        f[i + 1] += f[i];
      }
      if(i >= 1 && (s[i - 1] - '0') * 10 + s[i] - '0' <= 26 && s[i - 1] != '0') {
                f[i + 1] += f[i - 1];
            }
        }
        return f[l];
    }
};